# -*- coding: latin-1 -*-
# Copyright (c) 2007-2009 Jorge Ortiz Romo <jortizromo@gmail.com>
#                         Freymam Vallejo Cuero <freturn@gmail.com>
# Permission is hereby granted, free of charge, to any person
# obtaining a copy of this software and associated documentation
# files (the "Software"), to deal in the Software without
# restriction, including without limitation the rights to use,
# copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the
# Software is furnished to do so, subject to the following
# conditions:

# The above copyright notice and this permission notice shall be
# included in all copies or substantial portions of the Software.

# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
# OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
# HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
# WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
# OTHER DEALINGS IN THE SOFTWARE.


'''
Created on Dec 7, 2009

@author: Freymam Vallejo
@author: Jorge Ortiz
'''

import Paths

def digraph_isReachable(digraph, start, end):
    """
    Indicates if node end is reachable from node start. Does have node start any path to node end?

    @type graph: digraph.
    @param graph: DiGraph.

    @type start: node
    @param start: initial node on the path

    @type end: node
    @param end: finish node on the path

    @rtype: bool.
    @return: True: if exists some path between both nodes. False: if doesn't exists.
    """

    #Gets all paths between node start and node end
    paths = Paths.digraph_find_all_paths(digraph, start, end)
    if len(paths) > 0:
        return True
    return False

def digraph_connectivity_nodal(digraph, start, end):
    """
	it brings connectivity information between node start and node end.
	
	@type start: node
    @param start: initial node on the path

    @type end: node
    @param end: finish node on the path
	
	@rtype: string.
    @return: Weakly connected: if exists some path between both nodes. Unilaterally connected: if doesn't exists. Strongly connected: if... Recursively connected: if.
	
    """

    #Gets all paths between node start and node end
    paths_start_to_end = Paths.digraph_find_all_paths(digraph, start, end)
    paths_end_to_start = Paths.digraph_find_all_paths(digraph, end, start)
    #Gets all paths between node start and node end
    semipaths = Paths.digraph_find_all_semipaths(digraph, start, end)
    #Output
    connectivity = ""

    #There is just semipaths
    if len(semipaths) > 0 and len(paths_start_to_end) == 0:
        connectivity = "Weakly connected"
        
    #There is just paths from only one both node start or end
    if len(paths_start_to_end) > 0 and len(paths_end_to_start) == 0:
        connectivity = "Unilaterally connected"
        
    #There is just paths from only one both node start or end
    if len(paths_start_to_end) == 0 and len(paths_end_to_start) > 0:
        connectivity = "Unilaterally connected"

    #There is paths from both to both
    if len(paths_start_to_end) > 0 and len(paths_end_to_start) > 0:
        connectivity = "Strongly connected"

    #Comparing one to one nodes in PathsTo and PathsFrom. 
    for pathTo in paths_start_to_end:
        isEqualToFrom = False
        for pathFrom in paths_end_to_start:
            pathFrom.reverse()
            if pathTo == pathFrom:
                isEqualToFrom = True
        if isEqualToFrom:
            connectivity = "Recursively connected"
            break

    #If dont have value, the I propose the Ordinary Connected
    if connectivity == "": connectivity = "No connected"

    return connectivity
        
def digraph_connectivity(digraph):
    """
	it brings connectivity information of all the network
	
	@type start: node
    @param start: initial node on the path

    @type end: node
    @param end: finish node on the path
	
	@rtype: string.
    @return: Weakly connected: if exists some path between both nodes. Unilaterally connected: if doesn't exists. Strongly connected: if... Recursively connected: if.
    """

    connections = {"No connected":1, "Weakly connected":2, "Unilaterally connected":3, "Strongly connected":4, "Recursively connected":5}
    back_connections = {1:"No connected", 2:"Weakly connected", 3:"Unilaterally connected", 4:"Strongly connected", 5:"Recursively connected"}
    connectivity = connections["Recursively connected"]
    
    for start in digraph:
        for end in digraph:
            if start != end:
                connect = digraph_connectivity_nodal(digraph, start, end)
                if connections[connect] < connectivity:
                    connectivity = connections[connect]
    return back_connections[connectivity]
    
